package com.hy;

import java.util.Arrays;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:设计可以求最短路径的图类
 * User:Mr.Du
 * Date:2024/3/26
 * Time:22:40
 */
public class Graphs {

    int INF = Integer.MAX_VALUE >> 1;
    int[][] g; // 邻接矩阵，值为边权
    int[] dis;
    int n;

    public Graphs(int nn, int[][] edges) {
        n = nn;
        g = new int[n][n];
        dis = new int[n + 1];
        for (int[] row : g) Arrays.fill(row, INF);
        for (int[] e : edges) addEdge(e);
    }

    public void addEdge(int[] e) {
        g[e[0]][e[1]] = e[2];
    }

    public int shortestPath(int start, int end) {
        Arrays.fill(dis, INF);
        dis[start] = 0;
        boolean[] vis = new boolean[n];
        while (true) {
            int x = n; //最近新可达点，初始化为不存在的点
            for (int i = 0; i < n; i++)
                if (!vis[i] && (dis[i] < dis[x]))
                    x = i;
            if (dis[x] == INF) return -1; //新可达点不存在
            if (x == end) return dis[x]; // 找到终点，提前退出
            vis[x] = true; // 在后续无需更新 x 到其余点的最短路
            // 更新最短路长度
            for (int y = 0; y < n; y++) dis[y] = Math.min(dis[y], dis[x] + g[x][y]);
        }
    }
}
